//山峰数组的顶部
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        //先写判断条件 写出来是r=mid 则在求mid时不用+1
        //写出来是l=mid时 则在求mid时用+1
        int l=0,r=arr.size()-1;
        while(l<r)
        {
            //求左边界
            int mid=(l+r)/2;
            if(arr[mid] <= arr[mid+1]) l=mid+1;
            else r=mid; 
        }
        return l;
    }
};
//狒狒吃香蕉
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) 
    {
        int maxspeed=0;
        for(auto e:piles) maxspeed=max(maxspeed,e);
        int l=1,r=maxspeed;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(canFinish(piles,h,mid))
            {
                r=mid;
            }
            else
            {
                l=mid+1;
            }
        }
        return l;
    }
    bool canFinish(vector<int>& piles,int h ,int k)
    {
        int time=0;
        for(auto e:piles)
        {
            //ceil 向上取整函数
            time+=ceil((double)e/k);
        }
        return time<=h;
    }
};
//排序数组中只出现一次的数字
class Solution {
public:
    // 1 1 2 3 3 4 4 8 8
    // 0 1 2 3 4 5 6 7 8
    // {1， 1} 、{2， 3} 、{3， 4} 、{4， 8} 、{8}
    //发现，因为缺失一个 2 所以使 {1, 1} 之后的数对都不由相同的数字组成的
    //所以需要找的就是 第一个不同的数对
    

    int singleNonDuplicate(vector<int>& nums) 
    {
        if(nums.size()==1) return nums[0];
        //最后一组一定是单着的 不管
        //l和r对应的是组数
        int l=0,r=nums.size()/2-1;
        while(l<r)
        {
            int mid=(l+r)/2;
            int index=2*mid;
            if(nums[index]==nums[index+1])
            {
                l=mid+1;
            }
            else
            {
                r=mid;
            }
        }
        if(nums[2*l]==nums[2*l+1])
        {
            //说明 单着的那个是出现一次的数据
            return nums.back();
        }
        else 
        { 
            return nums[2*l];
        }
    }
};